Puzzles as Resources
Volume Number: 2
Issue Number: 3
Column Tag: Developer's Forum
Puzzles as Resources in Aztec C
By David Levner, Sabaki Corp., Product: Polyomino Puzzles
Polyomino Puzzle Resources
Synopsis
Sam Loyd created polyomino puzzles 80 years ago. He didn't have a Macintosh, so
he made his puzzles out of cardboard. I am lucky to own a Mac, so I wrote the game
MacPoly to draw polyominoes on the screen.
MacPoly stores polyomino puzzles as resources, in a format described in this
article. A method for creating these resources is presented, enabling you to add your
own puzzles to MacPoly. The method may also be used to create other custom resources.
The word 'polyomino' is a generalization of 'domino'. A domino is made of two
squares, and a polyomino many squares. Here are some polyominoes:
Figure 1
An easy puzzle is shown below. The object is to cover the white square (the
solution shape) with the four gray pieces. Most polyomino puzzles are much more
difficult.
6 x 6 Square
Figure 2
Puzzle Source Files
The first step in creating a puzzle is to enter a puzzle source file. For example,
this is the source file I used to generate figure 2:
6 x 6 Square Congratulations! Puzzle by David Levner.
..................
.a.a..SSSSSS..b.b.
.aaaa.SSSSSS.bbbb.
.aaa..SSSSSS..bbb.
......SSSSSS......
.c.c..SSSSSS..d.d.
.cccc.SSSSSS.dddd.
.ccc..SSSSSS..ddd.
..................
Figure 3
Use a mono-spaced font, like Monaco to make the columns line up, and save the
file as text only. The first line of the file contains the puzzle name, followed by a
congratulatory message that is displayed when the puzzle is solved. Then begins the
puzzle grid.
The grid contains letters that stand for the squares of polyominoes. Lower case
letters represent squares that are outside the solution shape, and upper case letters,
except 'S', are squares covering the solution (none are shown in this example).
Non-alphabetic characters (the dots) are empty spaces that are not part of the solution
, and the letter 'S' denotes the squares of the solution that are not covered by any
polyominoes.
Solution Source Files
The solution to a puzzle is represented by a very similar source file. The only
difference is that there is no congratulatory message.
6 x 6 Square Solution
........
.AAABBB.
.AABBBB.
.AAABDB.
.CACDDD.
.CCCCDD.
.CCCDDD.
........
Figure 4
Puzzle and Solution Resources
A program could read these source files directly, but that would be less efficient
than reading resources on the Mac. At the end of this article, a program is listed to
convert puzzle and solution source files into resources.
MacPoly's puzzles are divided into 9 categories. Puzzle resources have type
SBPn, where n is a digit from 1 to 9, and solutions have type SBSn.
Resource Type Puzzle Type
SBP1 ˜Easy puzzles
SBP2 ˜Rectangles
SBP3 ˜Almost Rectangles
SBP4 ˜Parallelograms
SBP5 ˜Chess Boards
SBP6 ˜Polyominoes
SBP7 ˜Chess Pieces
SBP8 ˜Objects
SBP9 ˜Impossible Puzzles
Figure 5
The puzzle resource for 6 x 6 Square looks like this.
Congratulations! Puzzle by David Levner.
..................
.a.a..SSSSSS..b.b.
.aaaa.SSSSSS.bbbb.
.aaa..SSSSSS..bbb.
......SSSSSS......
.c.c..SSSSSS..d.d.
.cccc.SSSSSS.dddd.
.ccc..........ddd.
..................
..................
.a.a..SSSSSS..b.b.
.aaaa.SSSSSS.bbbb.
.aaa..SSSSSS..bbb.
......SSSSSS......
.c.c..SSSSSS..d.d.
.cccc.SSSSSS.dddd.
.ccc..........ddd.
..................
000000000
000000000
999999999
999999999
\0
Figure 6
The first line of the puzzle source file becomes the resource name. The second
copy of the puzzle grid reserves space to store an arrangement of the pieces saved with
MacPoly's save command.
Following the second grid are four nine digit numbers, representing (1) the
time spent to arrive at the saved position, in seconds, (2) the number of operations
performed to arrive at the saved position (MacPoly allows you to select a piece, drag it,
flip it, and spin it), (3) the record time to solve the puzzle, in seconds, and (4) the
record (fewest) number of operations to solve a puzzle. Initially, these numbers are
set to 0, 0, 999999999, and 999999999. At the end of the resource is a binary zero.
A solution resources differs in several ways: there is no congratulations message
or timing information, and only one puzzle grid.
Converting Source Files To Resources
I wrote a C program, called ftor, to convert puzzle source files to resources.
Ftor is designed to run under a shell program; it cannot be run from the Macintosh
desktop. If you try to recreate ftor, you should run it from the shell supplied with
your C compiler.
Most shell programs are modeled on the Bourne shell from the Unix operating
system. To use a shell, you type a command, which is interpreted as a program name
followed by an argument list. All the C compilers I have seen for the Mac include a
shell user interface. On the Amiga, Commodore supplies a shell called the Command
Line Interface.
I have listed below some dialogs with the shell. The '$' is a prompt character,
signifying that the shell is ready to accept a command. I typed the characters following
the '$' to run the program ftor; the line below contains the program's output. In this
case, I ran ftor without any arguments to remind me what arguments it expects.
$ ftor
usage: ftor TYPE outfile infile1 [infile2 ...]
Ftor's first argument is the four letter type of the resource(s) being created,
followed by the output file, and one or more puzzle source files. Each source file is
converted to a resource and stored in the output file.
Referenced by (2):